import sys
from tools import *

# 定义一个函数，用于查找距离最短节点
def find_min_distance(distances, visited):
    # 初始化最小距离和最小索引
    min_distance = sys.maxsize
    min_index = -1

    # 遍历距离列表，查找最小距离和最小索引
    for i in range(len(distances)):
        # 如果距离小于最小距离，且未被访问
        if distances[i] < min_distance and not visited[i]:
            # 更新最小距离和最小索引
            min_distance = distances[i]
            min_index = i

    # 返回最小索引
    return min_index

# 定义一个函数，用于使用Dijkstra算法求解最短距离
def dijkstra(graph, start):
    # 获取图中的节点数量
    num_nodes = len(graph)
    # 初始化距离列表，visited列表，previous列表
    distances = [sys.maxsize] * num_nodes
    visited = [False] * num_nodes
    previous = [None] * num_nodes  # 添加一个用于记录前一个节点的列表
    # 距离列表中，起点到起点的距离为0
    distances[start] = 0

    # 循环n次，每次循环找到距离最短节点，并更新距离列表，visited列表，previous列表
    for _ in range(num_nodes):
        # 调用find_min_distance函数，查找距离最短节点
        u = find_min_distance(distances, visited)
        # 将该节点标记为已访问
        visited[u] = True

        # 遍历图中的每个节点
        for v in range(num_nodes):
            # 如果该节点未被访问，且图中的两个节点之间有边，且距离列表中该节点到起点的距离大于起点到该节点的距离加上图中两个节点之间的距离
            if (
                not visited[v] and
                graph[u][v] != 0 and
                distances[u] + graph[u][v] < distances[v]
            ):
                # 更新距离列表中该节点到起点的距离
                distances[v] = distances[u] + graph[u][v]
                # 更新previous列表中该节点的前一个节点
                previous[v] = u  # 更新前一个节点

    # 返回距离列表和previous列表
    return distances, previous  # 返回最短距离和前一个节点列表

# 定义一个函数，用于获取最短路径
def get_shortest_path(previous, start, end):
    # 初始化最短路径列表
    path = []
    # 初始化当前节点
    current = end

    # 循环，直到当前节点为起点
    while current != start:
        # 将当前节点添加到最短路径列表中
        path.append(current)
        # 更新当前节点
        current = previous[current]

    # 将起点添加到最短路径列表中
    path.append(start)
    # 将最短路径列表反转
    path.reverse()

    # 返回最短路径列表
    return path

# 定义一个图
# graph = [
#     [0, 4, 2, 0, 0, 0],
#     [4, 0, 1, 5, 0, 0],
#     [2, 1, 0, 8, 10, 0],
#     [0, 5, 8, 0, 2, 6],
#     [0, 0, 10, 2, 0, 3],
#     [0, 0, 0, 6, 3, 0]
# ]
graph = getMartix()

# 定义起点和终点
start_node = 0
end_node = 34

# 调用dijkstra函数，求解最短距离
distances, previous = dijkstra(graph, start_node)
# 调用get_shortest_path函数，获取最短路径
shortest_path = get_shortest_path(previous, start_node, end_node)

# 打印最短距离
print("最短距离：", distances)
# 打印最短路径
print("最短路径：", shortest_path)

def getPath():
    return shortest_path